package be.ulb.f203.projet.tools;

import be.ulb.f203.projet.metier.Arc;
import be.ulb.f203.projet.metier.Chemin;
import be.ulb.f203.projet.metier.DijkstraResult;
import be.ulb.f203.projet.metier.Graphe;
import be.ulb.f203.projet.metier.Noeud;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 *
 * @author Srk
 */
public class GraphAlgorithms {

    /**
     * Execute l'algorithme de Dijkstra permettant de trouver les plus courts
     * chemins d'une racine vers tous les autres noeuds du graphe.
     *
     * @param graphe Graphe sur lequel l'algorithme est appliqué.
     * @param racine Racine du graphe.
     * @return Les plus courts chemins de la racine vers tous les autres noeuds
     * du graphe
     */
    public static DijkstraResult executeDijkstra(Graphe graphe, Noeud racine) {
        Set fileM = new HashSet();
        //Liste contenant la plus courte distance entre le noeud s et le noeud dist[i]
        double[] dist = new double[graphe.getOrder()];
        //Liste contenant le sommet précédent le noeud pred[i] sur le plus court chemin en construction entre le noeud s et le noeud pred[i]
        Noeud[] prec = new Noeud[graphe.getOrder()];
        //Liste des noeuds ayant déjà été visités
        boolean[] visited = new boolean[graphe.getOrder()];

        for (int i = 0; i < graphe.getOrder(); i++) {
            double poids = Double.POSITIVE_INFINITY;
            Noeud n = (Noeud) graphe.getNoeuds().get(i);
            Arc arc = graphe.getArc(racine, n);
            if (arc != null) {
                poids = arc.getPoids();
            }
            dist[i] = poids;
            prec[i] = racine;
            fileM.add(graphe.getNoeud(i));
        }

        //on retire le sommet s de la file
        fileM.remove(racine);

        //tant que la file n'est pas vide
        while (!fileM.isEmpty()) {
            final int min = minSommet(dist, visited);
            visited[min] = true;
            Noeud m = graphe.getNoeud(min);
            fileM.remove(m);

            if (dist[min] == Double.POSITIVE_INFINITY) {
                fileM.clear();
            } else {
                List<Noeud> voisins = m.getVoisins();
                for (int i = 0; i < voisins.size(); i++) {
                    Noeud noeud = voisins.get(i);
                    if (fileM.contains(noeud)) {
                        Arc arc = graphe.getArc(m, noeud);
                        double value = dist[min] + (double) arc.getPoids();
                        int indexOfNoeud = graphe.getNoeuds().indexOf(noeud);
                        if (value < dist[indexOfNoeud]) {
                            dist[indexOfNoeud] = value;
                            prec[indexOfNoeud] = m;
                        }
                    }
                }
            }
        }

        return new DijkstraResult(dist, prec, graphe);
    }

    private static int minSommet(double[] dist, boolean[] visited) {
        Double valeurMin = Double.POSITIVE_INFINITY;
        int indiceMin = 0;
        for (int i = 0; i < dist.length; i++) {
            if (!visited[i] && dist[i] <= valeurMin) {
                indiceMin = i;
                valeurMin = dist[i];
            }
        }
        return indiceMin;
    }

    /**
     * Retourne le chemin le plus court passant par tous les noeuds du graphe en
     * commençant par la racine.
     *
     * @param graphe Graphe sur lequel l'algorithme est appliqué.
     * @param racine Racine du graphe.
     * @return Le chemin le plus court passant par tous les noeuds du graphe.
     */
    public static Chemin findPathAllNodes(Graphe graphe, Noeud racine) {
        Noeud[] chemin = new Noeud[graphe.getOrder()];
        List<Noeud[]> solutions = new ArrayList<>();
        backtracking(chemin, graphe, racine, 0, solutions);
        Chemin cheminMin = null;
        double coutMin = Double.POSITIVE_INFINITY;
        for (Noeud[] solution : solutions) {
            Chemin chem = new Chemin(graphe, solution);
            double cout = chem.getCout();
            if (cout < coutMin) {
                coutMin = cout;
                cheminMin = chem;
            }
        }
        return cheminMin;
    }

    private static boolean backtracking(Noeud[] chemin, Graphe graphe, Noeud n, int etape, List<Noeud[]> solutions) {
        boolean reussi = false;
        if (estAcceptable(chemin, n)) {
            chemin[etape] = n;
            if (etape + 1 == graphe.getOrder()) {
                reussi = true;
            } else {
                List<Noeud> voisins = n.getVoisins();
                for (int i = 0; i < voisins.size(); i++) {
                    reussi = backtracking(chemin, graphe, voisins.get(i), etape + 1, solutions);
                    if (reussi) {
                        //Une solution trouvée ! Copie dans la liste de solutions.
                        solutions.add(chemin.clone());
                        //Pour continuer à chercher les autres solutions.
                        reussi = false;
                    }
                    chemin[etape + 1] = null;
                }
            }
        } else {
            return false;
        }
        return reussi;
    }

    private static boolean estAcceptable(Noeud[] chemin, Noeud n) {
        for (Noeud noeud : chemin) {
            if (noeud != null && noeud.equals(n)) {
                return false;
            }
        }
        return true;
    }
}
